package com.gxc.binarySearch;

/**
 * 搜索二维矩阵
 * 给你一个满足下述两条属性的 m x n 整数矩阵：
 *
 * 每行中的整数从左到右按非严格递增顺序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
 */
public class SearchMatrix {

    public static void main(String[] args) {
        searchMatrix(new int[][]{
                {1,3,5,7},
                {10,11,16,20},
                {23,30,34,50}
        }, 11);
        System.out.println("");
    }

    public static boolean searchMatrix(int[][] matrix, int target) {
        int mid = 0, left = 0, right = matrix.length-1;
        while (left <= right) {
            mid = ((right - left)>>1) + left;
            if (matrix[mid][0] == target) return true;
            else if (target < matrix[mid][0]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        int row=right;
        if (right < 0) {
            return false;
        }
        left = 0;
        right = matrix[0].length-1;
        while (left<=right) {
            mid = ((right - left)>>1) + left;
            if (matrix[row][mid] == target) return true;
            else if (target < matrix[row][mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }

}
